import javax.xml.crypto.dsig.keyinfo.PGPData;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.TreeMap;

/***
 * 从m个元素中获取频率最高的前k个元素
 */
public class Solution {
    private class Freq implements Comparable<Freq> {
        int e;
        int freq;

        @Override
        public int compareTo(Freq o) {
            return this.freq < o.freq ? 1 : (this.freq > o.freq ? -1 : 0);
        }

        public Freq(int e,int freq){
            this.e = e;
            this.freq = freq;
        }
    }

    public List<Integer> topKFrequent(int[] nums, int k){
        //统计频率,放入treeMap
        TreeMap<Integer,Integer> map = new TreeMap<>();
        for(int num : nums){
            if(map.containsKey(num)){
                map.put(num,map.get(num) + 1);
            }else{
                map.put(num,1);
            }
        }

        //创建最大堆,存放自定义对象(包含元素和此元素的频数)
        PriorityQueue<Freq> pq = new PriorityQueue<Freq>();
        for(int key : map.keySet()){
            if(pq.getSize() < k){
                pq.enqueue(new Freq(key,map.get(key)));
            }else if(map.get(key) > pq.getFront().freq){
                pq.dequeue();
                pq.enqueue(new Freq(key,map.get(key)));
            }
        }

        //返回list
        List<Integer> res = new LinkedList<>();
        while(!pq.isEmpty()){
            res.add(pq.getFront().e);
        }
        return res;
    }
}
